#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;

int minimumTotal(vector<vector<int> > &triangle) 
{
  int ret=0;
  int row = triangle.size();
  if(row<1)
    return ret;
  if( row==1 && triangle[0].size()>0 )
    return triangle[0][0];

  vector<int> sum( triangle.back() );
  for(int irow = row-1; irow>0; --irow )
  {
    int len = triangle.at(irow).size();
    for( int j=0; j<len-1; ++j )
    {
      if( sum[j] < sum[j+1] )
      {
        sum[j] = sum[j] + triangle[irow-1][j];
      }
      else
      {
        sum[j] = sum[j+1] + triangle[irow-1][j];
      }
    }
  }


  return  sum[0];



}



int main(int argc,char *argv[])
{
  vector<vector<int>> t;
  t.push_back( vector<int>     {2} );
  t.push_back( vector<int>    {3,4} );
  t.push_back( vector<int>  {6,5,7} );
  t.push_back( vector<int> {4,1,8,3} );


  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  
  int ret = minimumTotal( t );

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;
  cout << ret << endl;


  return 0;
}
